package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 覃国强
 * @date 2022-05-19 17:21
 */
public class 题库_0020_有效的括号 {

  static
  class Solution {

    private static final Map<Character, Character> BRACKET_PAIRS = new HashMap<>();
    static {
      BRACKET_PAIRS.put(')', '(');
      BRACKET_PAIRS.put(']', '[');
      BRACKET_PAIRS.put('}', '{');
    }

    public boolean isValid(String s) {
      if (s == null || s.length() == 0) {
        return true;
      }
      if (s.length() % 2 != 0) {
        return false;
      }

      Deque<Character> stack = new ArrayDeque<>();
      for (char ch : s.toCharArray()) {
        if (ch == '(' || ch == '[' || ch == '{') {
          stack.push(ch);
        } else {
          if (notMatch(stack, ch)) {
            return false;
          }
          stack.pop();
        }
      }

      return stack.isEmpty();
    }

    private boolean notMatch(Deque<Character> stack, char ch) {
      return stack.isEmpty() || !stack.peek().equals(BRACKET_PAIRS.get(ch));
    }
  }

}
